package temp.二叉树.构造二叉树;

//给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并
//返回其根节点。
//
//
//
// 示例 1:
//
//
//输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
//输出: [3,9,20,null,null,15,7]
//
//
// 示例 2:
//
//
//输入: preorder = [-1], inorder = [-1]
//输出: [-1]
//
//
//
//
// 提示:
//
//
// 1 <= preorder.length <= 3000
// inorder.length == preorder.length
// -3000 <= preorder[i], inorder[i] <= 3000
// preorder 和 inorder 均 无重复 元素
// inorder 均出现在 preorder
// preorder 保证 为二叉树的前序遍历序列
// inorder 保证 为二叉树的中序遍历序列
//
//
// Related Topics 树 数组 哈希表 分治 二叉树 👍 1921 👎 0

import temp.二叉树.TreeNode;

/**
 * 从前序与中序遍历序列构造二叉树
 *
 * @author saint
 */
class P105_ConstructBinaryTreeFromPreorderAndInorderTraversal {
    public static void main(String[] args) {
        Solution solution = new P105_ConstructBinaryTreeFromPreorderAndInorderTraversal().new Solution();
        int[] preOrder = new int[]{3,9,20,15,7};
        int[] inOrder = new int[]{9,3,15,20,7};
        TreeNode treeNode = solution.buildTree(preOrder, inOrder);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //preOrder第一个点为根节点，在中序遍历中找到这个点，左边为左子树，右边为右子树
        TreeNode root = new TreeNode(preorder[0]);
        int inIndex = findIndex(inorder, root.val);//该节点左边为左子树，右边为右子树
        //切割前序数组的时候，和中序数组切割的左右不分长度相同
        root.left = buildTree(preorder,inorder,1,1+inIndex-1,0,inIndex-1);
        root.right = buildTree(preorder,inorder,1+inIndex,preorder.length-1,inIndex+1,inorder.length-1);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder,int preLeft,int preRight,int inLeft, int inRight){
        if((preLeft>preRight)||(inLeft>inRight)||preLeft>=preorder.length||preRight<0||inLeft>= inorder.length||inRight<0){
            return null;
        }
        TreeNode node = new TreeNode(preorder[preLeft]);
        int inIndex = findIndex(inorder, node.val);//前序最左为左子树根节点
        node.left=buildTree(preorder,inorder,preLeft+1,preLeft+1+inIndex-inLeft,inLeft,inIndex-1);
        node.right = buildTree(preorder,inorder,preLeft+1+inIndex-inLeft,preRight,inIndex+1,inRight);
        return node;
    }
    public int findIndex(int[] nums,int target){
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
